package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	Given an array of integers, find two numbers such that they add up to a specific target number.
　　The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. 
　　You may assume that each input would have exactly one solution. 
　　Input: numbers={2, 7, 11, 15}, target=9 
　　Output: index1=1, index2=2 
题目大意
	　　给定一个整数数组，找出其中两个数满足相加等于你指定的目标数字。 
　　要求：这个函数twoSum必须要返回能够相加等于目标数字的两个数的索引，
		且index1必须要小于index2。请注意一点，
		你返回的结果（包括index1和index2）都不是基于0开始的。
		注：你可以假设每一个输入肯定只有一个结果。 
解题思路
	
 * @Date 2017-09-14 23：43
 */
public class _109_Convert_Sorted_List_to_Binary_Search_Tree {
	
	/**
	 * 法一：暴力匹配：
	 * 			代码算法类似于选择排序
	 * @My:
	 * @param nums
	 * @return
	 */
	public int[] twoSum(int[] nums, int target) {
    	//题目当中指定了一定有解：且唯一
    	int[] rs = new int[2];	
    	int N = nums.length;
    	for (int i = 0; i < N-1; i ++) {
    		for (int j = i+1; j < N; j ++) {	//需要比较N-1次
    			if (nums[i]+nums[j] == target) {
    				rs[0] = i;
    				rs[1] = j;
    				break;
    			}
    		}
    	}

    	return rs;
    }
	
	/**
	 * 法二：
	 * 	这题不难，只需要熟悉hashtable即可。
	 * 在hashtable里面，key是差，value是index。
	 * 比如例子中的[2,7,11,15],target是9。那么在2的时候就存入7 0，
	 * 下一位找到7的时候，之前有个差值是7，那么就返回7对应的index，0，以及当前这个7的index，就是1。
	 * @param nums
	 * @return
	 */
	 public int[] twoSum2(int[] nums, int target) {
	        //创建一下数组，要存两个index的数组。
	        int[] result = new int[2];
	        //这里用hashtable也行，看心情。
	        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	        //扫一遍数组，一边扫一边存
	        for(int i = 0; i < nums.length; i++){
	            int cur = nums[i];
	            //这里搞出来个差值，其实差值是在没找到之后添加到map里面的。
	            int toFind = target - cur;
	            //如果发现之前需要这个差值，那就找index。
	            if(map.containsKey(cur)){
	                result[0] = map.get(cur);
	                result[1] = i;
	            	traverse(result);
	                return result;
	            }
	            //如果没有，就put到map里面
	            else{
	                map.put(toFind, i);
	            }
	        }
	
	        return result;
	    }
	public void traverse(int[] nums) {
		for (int i : nums) {
			LogUtils.print(i);
		}
	}
    
	public static void main(String[] args) {
		_109_Convert_Sorted_List_to_Binary_Search_Tree obj = new _109_Convert_Sorted_List_to_Binary_Search_Tree();
//		obj.twoSum(new int[]{1, 2, 3, 4, 5, 6, 7}, 7);
//		obj.twoSum2(new int[]{2, 7, 11, 15}, 9);
		obj.twoSum2(new int[]{3, 2, 4}, 6);
	}

}
